package com.yubest;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个整数数组 distance 。
 * <p>
 * 从 X-Y 平面上的点 (0,0) 开始，先向北移动 distance[0] 米，然后向西移动 distance[1] 米，向南移动 distance[2] 米，向东移动 distance[3] 米，持续移动。也就是说，每次移动后你的方位会发生逆时针变化。
 * <p>
 * 判断你所经过的路径是否相交。如果相交，返回 true ；否则，返回 false 。
 * <p>
 *  
 * <p>
 * 示例 1：[图片] img/0335_1.jpg
 * <p>
 * <p>
 * 输入：distance = [2,1,1,2]
 * 输出：true
 * 示例 2：[图片] img/0335_2.jpg
 * <p>
 * <p>
 * 输入：distance = [1,2,3,4]
 * 输出：false
 * 示例 3：[图片] img/0335_3.jpg
 * <p>
 * <p>
 * 输入：distance = [1,1,1,1]
 * 输出：true
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= distance.length <= 105
 * 1 <= distance[i] <= 105
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/self-crossing
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/10/29 16:27
 */
public class P0335 {

    public static void main(String[] args) {
        System.out.println(new Solution335().isSelfCrossing(new int[]{2, 1, 1, 2}));

        System.out.println(new Solution335().isSelfCrossing(new int[]{1, 2, 3, 4}));

        System.out.println(new Solution335().isSelfCrossing(new int[]{1, 1, 1, 1}));

        System.out.println(new Solution335().isSelfCrossing(new int[]{1, 1, 2, 1, 1}));

        System.out.println(new Solution335().isSelfCrossing(new int[]{3, 3, 4, 2, 2}));

    }
}

class Solution335 {

    //todo 超时
    public boolean isSelfCrossing(int[] distance) {
        List<Line> lines = new ArrayList<>();
        //记录上一次的结束点
        Point prePoint = new Point(0, 0);
        Point point = null;
        for (int i = 0; i < distance.length; i++) {
            if (i % 4 == 0) {
                point = new Point(prePoint.getX(), prePoint.getY() + distance[i]);
            } else if (i % 4 == 1) {
                point = new Point(prePoint.getX() - distance[i], prePoint.getY());
            } else if (i % 4 == 2) {
                point = new Point(prePoint.getX(), prePoint.getY() - distance[i]);
            } else if (i % 4 == 3) {
                point = new Point(prePoint.getX() + distance[i], prePoint.getY());
            }
            lines.add(new Line(i, prePoint, point));
            prePoint = point;
        }
        Line l1 = null;
        Line l2 = null;
        for (int i = 0; i < lines.size(); i++) {
            l1 = lines.get(i);
            for (int j = i + 2; j < lines.size(); j++) {
                l2 = lines.get(j);
                //l1如果是横线
                if (l1.getStart().getY().equals(l1.getEnd().getY())) {
                    //l2如果是横线
                    if (l2.getStart().getY().equals(l2.getEnd().getY())) {
                        //如果Y不相同，则继续下次
                        if (!l1.getStart().getY().equals(l2.getStart().getY())) {
                            continue;
                        }
                        if (l1.getStart().getX() >= l2.getStart().getX() && l1.getStart().getX() <= l2.getEnd().getX()
                                || l1.getEnd().getX() >= l2.getStart().getX() && l1.getEnd().getX() <= l2.getEnd().getX()
                                || l2.getStart().getX() >= l1.getStart().getX() && l2.getStart().getX() <= l1.getEnd().getX()
                                || l2.getEnd().getX() >= l1.getStart().getX() && l2.getEnd().getX() <= l1.getEnd().getX()) {
                            System.out.println("===:" + l1.getIndex() + ", " + l2.getIndex());
                            return true;
                        }
                    }
                    //l2如果是竖线
                    else {
                        if (l1.getStart().getY() >= l2.getStart().getY() && l1.getStart().getY() <= l2.getEnd().getY()
                                && l2.getStart().getX() >= l1.getStart().getX() && l2.getStart().getX() <= l1.getEnd().getX()) {
                            System.out.println("===:" + l1.getIndex() + ", " + l2.getIndex());
                            return true;
                        }
                    }
                }
                //l1是竖线
                else {
                    //l2如果是竖线
                    if (l2.getStart().getX().equals(l2.getEnd().getX())) {
                        //如果X不相同，则继续下次
                        if (!l1.getStart().getX().equals(l2.getStart().getX())) {
                            continue;
                        }
                        if (l1.getStart().getY() >= l2.getStart().getY() && l1.getStart().getY() <= l2.getEnd().getY()
                                || l1.getEnd().getY() >= l2.getStart().getY() && l1.getEnd().getY() <= l2.getEnd().getY()
                                || l2.getStart().getY() >= l1.getStart().getY() && l2.getStart().getY() <= l1.getEnd().getY()
                                || l2.getEnd().getY() >= l1.getStart().getY() && l2.getEnd().getY() <= l1.getEnd().getY()) {
                            System.out.println("===:" + l1.getIndex() + ", " + l2.getIndex());
                            return true;
                        }
                    }
                    //l2如果是横线
                    else {
                        if (l1.getStart().getX() >= l2.getStart().getX() && l1.getStart().getX() <= l2.getEnd().getX()
                                && l2.getStart().getY() >= l1.getStart().getY() && l2.getStart().getY() <= l1.getEnd().getY()) {
                            System.out.println("===:" + l1.getIndex() + ", " + l2.getIndex());
                            return true;
                        }
                    }
                }
            }
        }
        //判断竖线是否有交叉
        return false;
    }

}

class Line {

    private Integer index;

    private Point start;

    private Point end;

    public Integer getIndex() {
        return index;
    }

    public void setIndex(Integer index) {
        this.index = index;
    }

    public Line(Integer index, Point p1, Point p2) {
        this.index = index;
        //将线的方向转换为从左到右，从下到上的方向
        if (p1.getX().equals(p2.getX())) {
            if (p1.getY() < p2.getY()) {
                this.start = new Point(p1.getX(), p1.getY());
                this.end = new Point(p2.getX(), p2.getY());
            } else {
                this.start = new Point(p2.getX(), p2.getY());
                this.end = new Point(p1.getX(), p1.getY());
            }
        } else {
            if (p1.getX() < p2.getX()) {
                this.start = new Point(p1.getX(), p1.getY());
                this.end = new Point(p2.getX(), p2.getY());
            } else {
                this.start = new Point(p2.getX(), p2.getY());
                this.end = new Point(p1.getX(), p1.getY());
            }
        }
    }

    public Point getStart() {
        return start;
    }

    public void setStart(Point start) {
        this.start = start;
    }

    public Point getEnd() {
        return end;
    }

    public void setEnd(Point end) {
        this.end = end;
    }

}

class Point {

    private Integer x;

    private Integer y;

    public Point(Integer x, Integer y) {
        this.x = x;
        this.y = y;
    }

    public Integer getX() {
        return x;
    }

    public void setX(Integer x) {
        this.x = x;
    }

    public Integer getY() {
        return y;
    }

    public void setY(Integer y) {
        this.y = y;
    }
}
